#include<vector>
#include<stack>
using namespace std;
class Solution {
    vector<vector<int>>ops = { {1,0},{-1,0},{0,1},{0,-1} };
    void helper1(const vector<vector<int>>& matrix, vector<vector<int>>& flag, int i, int j) {
        if (flag[i][j]==1)
            return;
        flag[i][j] = 1;
        int rows = matrix.size();
        int cols = matrix[0].size();
        stack<int>stack_;
        stack_.push(i * cols + j);
        while (!stack_.empty()) {
            auto p = stack_.top();
            stack_.pop();
            int i = p / cols;
            int j = p % cols;
            for (auto op : ops) {
                int r = i + op[0], c = j + op[1];
                if (r < 0 ||r >= rows || c < 0 || c >= cols|| flag[r][c]==1)
                    continue;
                if (matrix[i][j] <= matrix[r][c]) {
                    flag[r][c] = 1;
                    stack_.push(r * cols + c);
                }
            }
        }
    }

    void helper2(const vector<vector<int>>& matrix, vector<vector<int>>& flag, vector<vector<int>>& res, int i, int j) {
        if (flag[i][j] == 1) {
            res.push_back({ i,j });
        }
        if (flag[i][j] == 2)
            return;
        flag[i][j] = 2;
        int rows = matrix.size();
        int cols = matrix[0].size();
        stack<int>stack_;
        stack_.push(i * cols + j);
        while (!stack_.empty()) {
            auto p = stack_.top();
            stack_.pop();
            int i = p / cols;
            int j = p % cols;
            for (auto op : ops) {
                int r = i + op[0], c = j + op[1];
                if (r < 0 || r >= rows || c < 0 || c >= cols || flag[r][c] == 2)
                    continue;
                if (matrix[i][j] <= matrix[r][c]) {
                    if(flag[r][c]==1)
                        res.push_back({ r,c });
                    flag[r][c] = 2;
                    stack_.push(r * cols + c);
                }
            }
        }
    }



public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        vector<vector<int>>res;
        if (matrix.size() < 1)return res;
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<int>> flag(rows);
        for (int i = 0; i < rows; ++i)
            flag[i].resize(cols);
        for (int i = 0; i < rows; ++i) 
            helper1(matrix, flag, i, 0);
        for (int i = 0; i < cols; ++i) 
            helper1(matrix, flag, 0, i);
        for (int i = 0; i < rows; ++i) 
            helper2(matrix, flag,res, i, cols-1);
        for (int i = 0; i < cols; ++i) 
            helper2(matrix, flag, res,rows-1, i);
        return res;
    }
};